package org.example.leetcode;

import java.util.Arrays;

/**
 * <a href="https://leetcode.cn/problems/3sum-closest/">最接近的三数之和</a>
 * @author shenguangyang
 */
public class N016_ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        int length = nums.length;
        int distance = Math.abs(target - (nums[0] + nums[1] + nums[2]));
        int result = nums[0] + nums[1] + nums[2];
        Arrays.parallelSort(nums);

        for (int i = 0; i < nums.length; i++) {
            int left = i + 1;
            int right = length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < target) {
                    left = left + 1;
                } else if (sum > target) {
                    right = right - 1;
                } else {
                    return sum;
                }
                // 计算距离
                int temp =  Math.abs(target - sum);
                if (temp < distance) {
                   distance = temp;
                   result = sum;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        N016_ThreeSumClosest threeSumClosest = new N016_ThreeSumClosest();
        int[] nums = new int[] {-1,2,1,-4};
        System.out.println(threeSumClosest.threeSumClosest(nums, 1));
    }
}
